﻿/*

 * Copyright (c) 2013 Diorge Brognara, Renan Peixoto

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE SOFTWARE.

*/
using System;
using System.Collections.Generic;
using System.Text;

namespace Grafos {
    /// <summary>
    /// Representa um vértice qualquer de um grafo
    /// </summary>
    public class Vértice {

        /// <summary>
        /// Nome de um vértice
        /// </summary>
        /// <remarks>Grafos não aceitam vértices com nome repetido</remarks>
        public string Nome { get; set; }

        /// <summary>
        /// Valor λ do vértice
        /// </summary>
        /// <remarks>A propriedade Lambda é um atalho para esta propriedade</remarks>
        /// <seealso cref="Lambda"/>
        public float λ { get; set; }
        /// <summary>
        /// Valor λ do vértice
        /// </summary>
        /// <remarks>É um atalho para a propriedade λ, para facilitar a digitação</remarks>
        /// <seealso cref="λ"/>
        public float Lambda { get { return λ; } set { λ = value; } }

        /// <summary>
        /// Predecessor do vértice
        /// </summary>
        /// <remarks>A propriedade Pi é um atalho para esta propriedade</remarks>
        /// <seealso cref="Pi"/>
        public Vértice π { get; set; }
        /// <summary>
        /// Predecessor do vértice
        /// </summary>
        /// <remarks>É um atalho para a propriedade π, para facilitar digitação</remarks>
        /// <seealso cref="π"/>
        public Vértice Pi { get { return π; } set { π = value; } }

        /// <summary>
        /// Valor qualquer, sem valor útil para o vértice
        /// </summary>
        /// <remarks>
        /// Essa propriedade se destina a algoritmos que utilizam valores associados aos vértices
        /// Por exemplo, o esquema de cores utilizados nos algoritmos de Busca em Profundidade e Busca em Largura
        /// </remarks>
        public object Tag { get; set; }

        /// <summary>
        /// Lista de arestas do vértice
        /// </summary>
        protected List<Aresta> Arestas { get; set; }

        /// <summary>
        /// Constrói um vértice a partir de um nome único
        /// </summary>
        /// <param name="nome">Nome-identificador único</param>
        public Vértice(string nome) {
            Nome = nome;
            Arestas = new List<Aresta>();
        }

        /// <summary>
        /// Retorna uma cópia das arestas que partem do vértice
        /// </summary>
        /// <returns>Uma cópia da lista de arestas</returns>
        /// <remarks>As arestas são modificáveis (cópia rasa), mas a lista de arestas não é</remarks>
        public List<Aresta> GetArestas() {
            return new List<Aresta>(Arestas);
        }

        /// <summary>
        /// Remove a aresta dada do registro do vértice
        /// </summary>
        /// <param name="a">Aresta a ser removida</param>
        public void RemoverAresta(Aresta a) {
            Arestas.Remove(a);
        }

        /// <summary>
        /// Adiciona uma nova aresta às conexões do vértice
        /// </summary>
        /// <param name="a">Aresta a ser adicionada</param>
        public void AdicionarAresta(Aresta a) {
            Arestas.Add(a);
        }

        /// <summary>
        /// Gera uma representação textual do vértice
        /// </summary>
        /// <returns>Vértice que descreve o nome do vértice e seus valores λ e π</returns>
        /// <remarks>
        /// Formato:
        /// [Nome] (λ=[λ]; π=[π])
        /// Se π for nulo:
        /// [Nome] (λ=[λ]; π=NIL)
        /// </remarks>
        public override string ToString() {
            StringBuilder sb = new StringBuilder();
            sb.Append(Nome == null ? string.Empty : Nome);
            sb.Append(" (λ=");
            sb.Append(λ);
            sb.Append("; π=");
            sb.Append(π == null ? "NIL" : π.Nome);
            sb.Append(")");
            return sb.ToString();
        }

        /// <summary>
        /// Procura uma aresta até um vértice alvo
        /// </summary>
        /// <param name="target">Vértice que deve ser a outra extremidade da aresta</param>
        /// <returns>A primeira aresta encontrada até o alvo</returns>
        /// <remarks>
        /// Se houver mais de uma aresta (paralelas), somente a primeira encontrada é retornada
        /// Veja o método ProcurarArestas (no plural) se este comportamente é inadequado para o caso
        /// </remarks>
        /// <example>
        /// Vértice v1 = new Vértice("A");
        /// Vértice v2 = new Vértice("B");
        /// Aresta a = new Aresta(v1, v2);
        /// v1.ProcurarAresta(v2).Equals(a); // true
        /// </example>
        /// <seealso cref="ProcurarArestas"/>
        public Aresta ProcurarAresta(Vértice target) {
            foreach (Aresta a in Arestas) {
                if ((a.Extremidade1.Equals(this) && a.Extremidade2.Equals(target))
                    || (a.Extremidade1.Equals(target) && a.Extremidade2.Equals(this)))
                    return a;
            }
            return null;
        }

        /// <summary>
        /// Procura todas as arestas entre este vértice e um vértice alvo
        /// </summary>
        /// <param name="target">Vértice que deve ser a outra extremidade das arestas</param>
        /// <returns>Uma lista de arestas que conectam este vértice ao alvo</returns>
        /// <remarks>Todas as arestas retornadas são paralelas entre si</remarks>
        /// <example>
        /// Vértice v1 = new Vértice("A");
        /// Vértice v2 = new Vértice("B");
        /// Aresta a = new Aresta(v1, v2);
        /// Aresta b = new Aresta(v1, v1);
        /// v1.ProcurarArestas(v2).Contains(a); // true
        /// v1.ProcurarArestas(v2).Contains(b); // true
        /// </example>
        public List<Aresta> ProcurarArestas(Vértice target) {
            List<Aresta> ret = new List<Aresta>();

            foreach (Aresta a in Arestas) {
                if ((a.Extremidade1.Equals(this) && a.Extremidade2.Equals(target))
                    || (a.Extremidade1.Equals(target) && a.Extremidade2.Equals(this)))
                    ret.Add(a);
            }

            return ret;
        }

        /// <summary>
        /// Calcula o grau do vértice
        /// </summary>
        /// <returns>Valor numérico maior que zero que representa o grau do vértice</returns>
        /// <remarks>Cada conexão adiciona 1 ao grau, mas se for loop, adiciona 2</remarks>
        /// <example>
        /// <code>
        /// Vértice v1 = new Vértice("V1");
        /// Vértice v2 = new Vértice("V2");
        /// Aresta a = new Aresta(v1, v2);
        /// Aresta b = new Aresta(v1, v1);
        /// // v1.Grau = 3
        /// </code>
        /// </example>
        public int Grau() {
            int grau = 0;
            foreach (Aresta a in Arestas) {
                grau++;
                if (a.ÉLoop)
                    grau++;
            }
            return grau;
        }

        /// <summary>
        /// Calcula os vértices vizinhos
        /// </summary>
        /// <returns>Todos os vértices que é possível chegar em um passo a partir deste</returns>
        /// <remarks>Um vértice nunca é seu próprio vizinho, mesmo que possua loop</remarks>
        /// <example>
        /// Vértice v1 = new Vértice("V1");
        /// Vértice v2 = new Vértice("V2");
        /// Aresta a = new Aresta(v1, v2);
        /// Aresta b = new Aresta(v1, v1);
        /// // v1.Vizinhança() = { v2 }
        /// </example>
        public List<Vértice> Vizinhança() {
            List<Vértice> vizinhança = new List<Vértice>();

            foreach (Aresta a in Arestas) {
                if (!a.ÉLoop) {
                    if (a.Extremidade1.Equals(this) && !vizinhança.Contains(a.Extremidade2))
                        vizinhança.Add(a.Extremidade2);
                    else if (a.Extremidade2.Equals(this) && !vizinhança.Contains(a.Extremidade1))
                        vizinhança.Add(a.Extremidade1);
                }
            }

            return vizinhança;
        }

        /// <summary>
        /// Diz se um vértice é folha, assumindo que esteja em uma árvore
        /// </summary>
        /// <returns>True se só houver um vizinho</returns>
        /// <remarks>Em outra palavras, verifica se existe um e somente um vizinho deste vértice</remarks>
        /// <example>
        /// <code>
        /// Vértice v1 = new Vértice("V1"); // v1.ÉFolha() = false
        /// Vértice v2 = new Vértice("V2");
        /// Vértice v3 = new Vértice("V3");
        /// Aresta a = new Aresta(v1, v2); // v1.ÉFolha() = true, v2.ÉFolha() = true, v3.ÉFolha() = false
        /// Aresta b = new Aresta(v2, v3); // v1.ÉFolha() = true, v2.ÉFolha() = false, v3.ÉFolha() = true
        /// Aresta c = new Aresta(v1, v3); // v1.ÉFolha() = false, v2.ÉFolha() = false, v3.ÉFolha() = false
        /// </code>
        /// </example>
        public bool ÉFolha() {
            return Vizinhança().Count == 1;
        }

        /// <summary>
        /// Cria um conjunto de vértices
        /// </summary>
        /// <param name="baseNome">Nome de base para os vértices</param>
        /// <param name="quantia">Quantos vértices devem ser criados</param>
        /// <returns>Um conjunto de vértices de tamanho [quantia]</returns>
        /// <remarks>
        /// O nome dos vértices será {baseNome}+{1}, {baseNome}+{2}, ..., {baseNome}+{quantia}
        /// Ver exemplo
        /// </remarks>
        /// <example>
        /// <code>
        /// Vértice[] v = Vértice.CriarConjuntoVértices("V", 5);
        /// // v = {V1, V2, V3, V4, V5}
        /// </code>
        /// </example>
        public static Vértice[] CriarConjuntoVértices(string baseNome, int quantia) {
            if (quantia <= 0)
                throw new ArgumentException("Deve ser criado ao menos um vértice");

            int i;
            Vértice[] vertices = new Vértice[quantia];

            for (i = 0; i < quantia; i++) {
                vertices[i] = new Vértice(baseNome + (i + 1));
            }

            return vertices;
        }

    }
}
